/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int n, m, cnt, cnt1;
int head[maxn];
int dis[maxn];
bool vis[maxn];
struct Side
{
    int u, v, val, next;
} side[maxn], side1[maxn];
int head1[maxn];
int dis1[maxn];
bool vis1[maxn];
struct node
{
    int dis, id;
    bool operator<(const node &oth) const
    {
        return dis > oth.dis;
    }
};
priority_queue<node> q;
void add(int u, int v, int val)
{
    side[cnt].u = u;
    side[cnt].v = v;
    side[cnt].val = val;
    side[cnt].next = head[u];
    head[u] = cnt++;
}
void add1(int u, int v, int val)
{
    side1[cnt1].u = u;
    side1[cnt1].v = v;
    side1[cnt1].val = val;
    side1[cnt1].next = head1[u];
    head1[u] = cnt1++;
}
void dijkstra()
{
    while (!q.empty())
        q.pop();
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    dis[1] = 0;
    memset(vis, 0, sizeof(vis));
    //vis[1] = 1;
    node tp;
    tp.id = 1;
    tp.dis = 0;
    q.push(tp);
    while (!q.empty())
    {
        tp = q.top();
        q.pop();
        if (vis[tp.id] == true)
            continue;
        vis[tp.id] = true;
        int u = tp.id;
        for (int i = head[u]; i != -1; i = side[i].next)
        {
            int v = side[i].v;
            int val = side[i].val;
            if (dis[v] > dis[u] + val)
            {
                //printf("dis %d %d %d\n", dis[v], dis[u], val);
                dis[v] = dis[u] + val;
                node tp1;
                tp1.id = v;
                tp1.dis = dis[v];
                q.push(tp1);
            }
        }
    }
}
void dijkstra1()
{
    while (!q.empty())
        q.pop();
    memset(dis1, 0x3f3f3f3f, sizeof(dis1));
    dis1[1] = 0;
    memset(vis1, 0, sizeof(vis1));
    //vis1[1] = 1;
    node tp;
    tp.id = 1;
    tp.dis = 0;
    q.push(tp);
    while (!q.empty())
    {
        tp = q.top();
        q.pop();
        if (vis1[tp.id] == true)
            continue;
        vis1[tp.id] = true;
        int u = tp.id;
        for (int i = head1[u]; i != -1; i = side1[i].next)
        {
            int v = side1[i].v;
            int val = side1[i].val;
            if (dis1[v] > dis1[u] + val)
            {
                dis1[v] = dis1[u] + val;
                node tp1;
                tp1.id = v;
                tp1.dis = dis1[v];
                q.push(tp1);
            }
        }
    }
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    cnt1 = 0;
    memset(head1, -1, sizeof(head1));
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            int u, v, val;
            scanf("%d%d%d", &u, &v, &val);
            add(u, v, val);
            add1(v, u, val);
        }
        dijkstra();
        dijkstra1();
        ll sum = 0;
        for (int i = 2; i <= n; i++)
        {
            //printf("%d %d %d\n", i, dis[i], dis1[i]);
            sum += (ll)dis[i] + (ll)dis1[i];
        }
        printf("%lld\n", sum);
    }
    getchar();
    getchar();
    return 0;
}
